package sort;

public class QuickSort {

    /**
     * sort A[p..r] in order
     * @param A array to be sorted
     * @param p first element's index of A
     * @param r last element's index of A
     */
    public static void quickSort(int[] A, int p, int r) {

        // check index p, r
        if (p < r) {
            int q = partition(A, p, r);

            if(p < q)
                quickSort(A, p, q-1);

            if(q < r)
                quickSort(A, q+1, r);
        }
    }

    /**
     * print all data of array A
     * @param title title to be printed
     * @param A array to be printed
     */
    public static void printData(String title, int[] A) {
        System.out.println(title);
        System.out.println(A.length);
        System.out.print("[");
        for (int i = 0; i < A.length; i++) {
            if(i > 0) System.out.print(",");
            System.out.print(A[i]);
        }
        System.out.println("]");
    }

    /**
     * exchange A[d1] with A[d2]
     * @param A array
     * @param d1 first element to be exchanged
     * @param d2 second element to be exchanged
     */
    private static void exchange(int[] A, int d1, int d2) {
        int temp = A[d1];
        A[d1] = A[d2];
        A[d2] = temp;
    }

    /**
     * find out the pivot's location pivotLoc and relocate all element so that A[p..pivotLoc-1] <= A[pivotLoc] <= A[pivotLoc+1..r]
     * @param A array to be sorted
     * @param p first element's index of array A
     * @param r last element's index of array A
     * @return pivot's location pivotLoc
     * @note sweep A from p to r
     */
    public static int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                i++;
                // exchange A[i] and A[j]
                exchange(A, i, j);
            }
        }

        // exchange A[i+1] and A[r]
        exchange(A, i+1, r);
        return i+1;
    }

    /**
     * find out the pivot's location pivotLoc and relocate all element so that A[p..pivotLoc-1] <= A[pivotLoc] <= A[pivotLoc+1..r]
     * @param A array to be sorted
     * @param p first element's index of array A
     * @param r last element's index of array A
     * @return pivot's location pivotLoc
     * @note sweep A from two side to center
     */
    public static int partition_2(int[] A, int p, int r) {
        int pivot = A[p];
        int low = p;
        int high = r;

        while (low < high) {
            while (low < high && A[high] >= pivot) { high--;}
            A[low] = A[high];
            while (low < high && A[low] <= pivot) {low++;}
            A[high] = A[low];
        }
        A[low] = pivot;
        return low;
    }
}
